package algorithm.leetcode.I1to100;

import algorithm.leetcode.ListNode;


/**
 * 反转链表II
 *
 * 核心是找到四个节点
 * 原链表 (head) -> ... -> beforeStart -> start -> ... -> end -> behindEnd -> ... -> (tail)
 * 其中 start 和 end 就是待反转的头和尾
 */

public class Q92 {

    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode fakeHead = new ListNode(-1);
        fakeHead.next = head;
        ListNode start = fakeHead, beforeStart = fakeHead, behindEnd = fakeHead;

        // 找到开始反转的点 start 以及前面一个点 beforeStart
        for (int i = 1; i <= left; i++) {
            if (i != left) beforeStart = beforeStart.next;
            start = start.next;
        }

        // 断开 beforeStart 的后面
        beforeStart.next = null;

        // 开始反转 index为left到right的节点,起点是start
        ListNode prev = null, curr = start, next = null;
        for (int i = 0; i <= right - left; i++) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        // 此时start到prev已经完成了反转,curr是结束反转的点的后面一个
        // 即原链表,(head) -> ... -> beforeStart -> start -> ... -> prev(end) -> curr(behindEnd) -> ... -> (tail)
        // 需要做的是把 beforeStart 的 next 定为 prev, start 的 next 定为 behindEnd
        behindEnd = curr;
        beforeStart.next = prev;
        start.next = behindEnd;

        return fakeHead.next;
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        Q92 q92 = new Q92();
        q92.reverseBetween(listNode1, 2, 4);
    }

}
